Field of the Invention
The disclosed embodiments generally relate to techniques for displaying polygons. More specifically, the disclosed embodiments relate to an efficient polygon-clipping technique that facilitates clipping polygons to reduce the data that needs to be processed to display a set of polygons within a moveable viewport.
Related Art
Many applications may require clipping of polygons that have large point counts. An example is a web-based choropleth map in which the user “drags” the map. This has the effect of repositioning a clip rectangle defined by the screen's viewport. When the user releases the drag event, the server responds by sending a portion of the geometry that is clipped out of the entire map geometry to fit just the viewport. This reduces the amount of data that must be transferred. Used in conjunction with a generalization technique such as the Ramer-Douglas-Peucker technique, the map can be viewed in sufficient detail for any desired clip.
One popular polygon-clipping technique is the Greiner-Hormann technique (GH). The GH polygon-clipping technique begins by finding all the points at which two polygons intersect. Given n vertices for the subject polygon and m vertices for the clip polygon, the step of finding the intersections requires O(m*n) time. This means that using the GH polygon-clipping technique can be time-consuming for choropleth maps that have large point counts, which can cause the clipping operation to introduce a noticeable lag when a user drags a choropleth map.
Hence, what is needed is an efficient polygon-clipping technique to facilitate re-positioning a screen's viewport.